/**
 * describe:
 *
 * @author chaP
 * @date 2019/03/19
 */
package CodingTest.AC20190319;

/**
 * 桶排序应用：
 * 给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

 如果数组元素个数小于 2，则返回 0。

 示例 1:

 输入: [3,6,9,1]
 输出: 3
 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
 示例 2:

 输入: [10]
 输出: 0
 解释: 数组元素个数小于 2，因此返回 0。
 */
public class maxGap {
    public static void main(String[] args) {
        int nums[] = {3,6,9,1};
        System.out.println(maxGap(nums));
    }
    public static int maxGap(int[] nums){
        if(nums == null|| nums.length<2){
            return 0;
        }
        int len = nums.length;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i =0;i<len;i++){
            max = Math.max(max,nums[i]);
            min = Math.min(min,nums[i]);
        }
        //最大值和最小值相等就返回0
        if(max == min){
            return 0;
        }
        //桶的编号
        int bid = 0;
        //三个平行数组，记录同一个编号，即同一个桶的信息
        int[] mins = new int[len+1];
        int[] maxs = new int[len+1];
        boolean[] hasNum = new boolean[len+1]; //创建这个boolean数组是为了后面的遍历方便
        for(int i = 0;i<len;i++){
            //数值桶装桶
            bid = bucket(nums[i],len,min,max);
            //每次比较桶内的最小值
            mins[bid] = hasNum[bid] ? Math.min(mins[bid],nums[i]) : nums[i];
            maxs[bid] = hasNum[bid] ? Math.max(maxs[bid],nums[i]):nums[i];
            hasNum[bid] = true;
        }
        int res = 0;
        //第一个桶的最大值，关键位置
        int lastMax = maxs[0];
        int i = 1;
        //小于等于len是因为比如三个数 四个桶，最大最小数放在第一个最后一个桶，这样就能把每一个桶遍历到
        for(;i<=len;i++){
            if(hasNum[i]){
                res = Math.max(res,mins[i]-lastMax);
                lastMax = maxs[i];
            }
        }
        return res;
    }
    public static int bucket(long num,long len,long min,long max){
        return (int)((num - min)*len/(max-min));
    }
}
